package pers.cfeng.server.versionManage;

import pers.cfeng.common.DatabaseException;
import pers.cfeng.common.ErrorCode;

import java.util.*;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

/**
 * 维护一个依赖等待图，使用死锁检测算法（判断环）进行死锁检测
 *
 */

public class LockTable {

    private Map<Long, List<Long>> tUList; //某个tid已经获得的资源列表
    private Map<Long, Long> u2t; //某个资源uid被tid持有
    private Map<Long, List<Long>> waitTList; //正在等待某资源的tid列表
    private Map<Long, Lock> waitLock; //正在等待资源的Tid的锁
    private Map<Long, Long> waitU; //TID正在等待的UID

    private Lock lock;

    private Map<Long, Integer> tidStamp;
    private int stamp;

    public LockTable() {
        tUList = new HashMap<>();
        u2t = new HashMap<>();  //uid已经被tid持有
        waitTList = new HashMap<>();
        waitLock = new HashMap<>();
        waitU = new HashMap<>();//tid等待uid
        lock = new ReentrantLock();
    }

    /**
     * 尝试向图中加入一条边，并进行死锁检测， 如果检测死锁，就撤销该边
     * 不需要等待就直接返回null，
     * 否则返回锁对象 【各个线程都会尝试加锁，锁对象直接放到waitLock中】
     * 会造成死锁就抛出异常
     */
    public Lock add(long tid, long uid) throws Exception {
        lock.lock();
        try {
            //如果uid已经被tid持有，那么就不需要等待, 直接返回null
            if(isInList(tUList, tid, uid))
                return null;
            if(!u2t.containsKey(uid)) {
                //uid没有被某个tid占有, 那么直接修改持有的Map和tid资源持有队列
                u2t.put(uid, tid);
                putIntoList(tUList, tid, uid);
                return null;
            }
            //已经被其他的tid占有，放入等待的Map和等待队列
            waitU.put(tid, uid);
            putIntoList(waitTList, uid, tid);
            //进行死锁检测
            if(hasDeadLock()) {
                //检查到就需要撤销该操作并且直接抛出异常
                waitU.remove(tid);
                removeFromList(waitTList, uid, tid);
                throw new DatabaseException(ErrorCode.DEAD_LOCK);
            }
            //没有死锁
            Lock lock = new ReentrantLock();
            lock.lock();
            waitLock.put(tid, lock);
            return lock;
        } finally {
            lock.unlock();
        }
    }

    public void remove(long tid) {
        lock.lock();
        try {
            List<Long> list = tUList.get(tid);
            if(list != null) {
                while (list.size() > 0) {
                    Long uid = list.remove(0);
                    selectNewTid(uid);
                }
            }
            waitU.remove(tid);
            tUList.remove(tid);
            waitLock.remove(tid);
        } finally {
            lock.unlock();
        }
    }

    //从等待队列中选择一个tid来占用该uid,从等待队列的头部0
    private void selectNewTid(long uid) {
        u2t.remove(uid); //资源取消占用
        List<Long> list = waitTList.get(uid);
        if(list == null || list.size() == 0)
            return;
        while (list.size() > 0) {
            long tid = list.remove(0);
            //当前tid没有获取到锁
            if(!waitLock.containsKey(tid)) {
                continue;
            }
            else {
                u2t.put(uid, tid);
                Lock lo = waitLock.remove(tid);
                waitU.remove(tid);
                lo.unlock();
                break;
            }
        }
        if(list.size() == 0)
            waitTList.remove(uid);
    }

    /**
     * 死锁检测
     */
    private boolean hasDeadLock() {
        tidStamp = new HashMap<>();
        stamp = 1;
        for(long tid : tUList.keySet()) {
            Integer s = tidStamp.get(tid);
            if(s != null && s > 0)
                continue;
            stamp ++;
            if(dfs(tid))
                return true;
        }
        return false;
    }

    /**
     * 检测tid以及其等待路线上前面的tid是否死锁
     */
    private boolean dfs(long tid) {
        Integer stp = tidStamp.get(tid);
        if(stp != null && stp == stamp)
            return true;
        if(stp != null && stp < stamp)
            return false;
        tidStamp.put(tid, stamp);

        Long uid = waitU.get(tid);
        if(uid == null)
            return false;
        Long t = u2t.get(uid);
        if(t == null)
            throw new DatabaseException("死锁检测中tid为null！");
        return dfs(t);
    }

    /**
     * 将tid1从tid0的队列中移除
     */
    private void removeFromList(Map<Long, List<Long>> listMap, long uid0, long uid1) {
        List<Long> list = listMap.get(uid0);
        if(list == null)
            return;
        Iterator<Long> iterator = list.iterator();
        while (iterator.hasNext()) {
            long el = iterator.next();
            if(el == uid1) {
                iterator.remove();
                break;
            }
        }
        if(list.size() == 0)
            listMap.remove(uid0);
    }


    /**
     * 将uid1放进uid0的队列中, 因为是队列但是这里采用的是List， 所以每次放在0位
     */
    private void putIntoList(Map<Long, List<Long>> listMap, long uid0, long uid1) {
        if(!listMap.containsKey(uid0))
            listMap.put(uid0, new ArrayList<>());
        listMap.get(uid0).add(0,uid1);
    }


    /**
     * 判断uid0的队列中是否包含uid1
     */
    private boolean isInList(Map<Long, List<Long>> listMap, long uid0, long uid1) {
        List<Long> list = listMap.get(uid0);
        if(list == null)
            return false;
        for (long el : list) {
            if (el == uid1)
                return true;
        }
        return false;
    }
}
